import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[]array={1,9,2,8,3,7,4,6,5};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort(int[] array, int left, int right) {
        if(left>=right)
             return;
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

    private static int partition(int[] nums, int left, int right) {
        int key = nums[left];
        int i = left;
        while(left<right){
            while(left<right&&nums[right]>=key){
                right--;
            }
            while (left<right&&nums[left]<=key){
                left++;
            }
            swap(nums,left,right);
        }
        swap(nums,left,i);
        return left;
    }

    private static void swap(int[] nums, int left, int right) {
         int tmp = nums[left];
         nums[left] = nums[right];
         nums[right] = tmp;
    }


}
